package com.algorithm.learning.base.图;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/29 22:05
 **/
public class 拓扑排序 {

    /**
     * 1、在图中找到所有入度为0的点 输出
     * 2、把所有入度为0的点在图中删掉，继续找入度为0的点输出，以此类推
     * 3、图中所有点都被删除后，依次输出的顺序就是拓扑排序
     *
     * 要求：有向图且没有环，（有环图或者无向图是没有拓扑排序的）
     * 应用：事件安排、编译顺序
     *
     * a -> b -> c -> e -> f
     *  ↘ -> -> ↗ ↘ -> t  ↙
     *
     *  上面的就是有向无环图，我们可以理解，事件的完成顺序
     *  1、做完a事情，才能做b，
     *  2、做完a和b两件事，才能做c，
     *  3、做完c事情，才能做e，
     *  4、做完e事情，才能做f，
     *  5、做完c和f两件事，才能做t
     *
     *  所以拓扑排序顺序：a, b, c, e, f, t
     *
     * @param graph
     */
    public static List<Node> sortedTopology(Graph graph) {
        // key: 某一个node
        // value: 剩余的入度
        Map<Node, Integer> inMap = new HashMap<>();
        // 剩余入度为0的点才能进队列
        Queue<Node> zeroInQueue = new LinkedList<>();
        // 遍历图中所有的点
        for (Node node : graph.nodes.values()) {
            // 初始化点和入度值
            inMap.put(node, node.in);
            // 入度为0，直接入队
            if (node.in == 0) {
                zeroInQueue.add(node);
            }
        }
        // 拓扑排序的结果，依次加入result
        List<Node> result = new LinkedList<>();
        while (!zeroInQueue.isEmpty()) {
            Node cur = zeroInQueue.poll();
            result.add(cur);
            for (Node next : cur.nexts) {
                // 删除cur对next的引用，所有cur的直接邻居点，入度-1
                inMap.put(next, inMap.get(next) - 1);
                // 如果next的入度变成0，加入队列
                if (inMap.get(next) == 0) {
                    zeroInQueue.add(next);
                }
            }
        }
        return result;
    }
}
